package com.njupt.backtracking;

import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/17 9:16
 * @Description: 491. 非递减子序列
 * @Version: 1.0
 */


public class FindSubsequences_491 {

    /**
     * 最外层收集的结果 使用HashSet这个数据结构
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences(int[] nums) {

        List<Integer> result = new LinkedList<>();
        int startIndex = 0;
        HashSet<List<Integer>> results = new HashSet<>();
        tracebacking(startIndex,nums,results,result);
        List<List<Integer>> resultss = new ArrayList<>(results);
        return resultss;
    }

    private void tracebacking(int startIndex, int[] nums, HashSet<List<Integer>> results, List<Integer> result) {

        if(result.size() >=2){
            results.add(new ArrayList(result));
        }
        if(startIndex == nums.length){
            return;
        }

        for (int i = startIndex; i < nums.length ; i++) {
            if(result.isEmpty()){
                result.add(nums[i]);
            }else {
                if(nums[i] >= result.get(result.size()-1)){
                    result.add(nums[i]);
                }else {
                    continue;
                }
            }
            tracebacking(i+1,nums,results,result);
            result.remove(result.size()-1);
        }
    }

    /**
     * 在每一层递归中都用
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences1(int[] nums){
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> path = new LinkedList<>();
        int startIndex = 0;

        tracebacking1(startIndex,nums,results,path);
        return results;
    }


    private void tracebacking1(int startIndex, int[] nums,  List<List<Integer>> results, List<Integer> path) {

        if(path.size() >=2){
            results.add(new ArrayList(path));
        }
        if(startIndex == nums.length){
            return;
        }
        Set<Integer> set = new HashSet<>();
        for (int i = startIndex; i < nums.length ; i++) {
            if(!path.isEmpty() && path.get(path.size()-1) > nums[i] || set.contains(nums[i])){
                continue;
            }
            set.add(nums[i]);
            path.add(nums[i]);
            tracebacking1(i+1,nums,results,path);
            path.remove(path.size()-1);

        }
    }

    public static void main(String[] args) {
        int[] nums = {4,6,7,7};
        FindSubsequences_491 test = new FindSubsequences_491();
        List<List<Integer>> results = test.findSubsequences1(nums);
        System.out.println(results);
    }
}
